package com.mlh.dp.knapsackProblem;

// 给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。
// 请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。
// 假设每一种面额的硬币有无限个。
// 题目数据保证结果符合 32 位带符号整数。
//
// 输入：amount = 5, coins = [1, 2, 5]
// 输出：4
// 解释：有四种方式可以凑成总金额：
// 5=5
// 5=2+2+1
// 5=2+1+1+1
// 5=1+1+1+1+1

public class MoneyChange {
    public static void main(String[] args) {
        int[] coins = {1, 2, 5};
        System.out.println(method3(5, coins));
    }

    //暴力递归  思路（硬币一个一个开放，开放的硬币由0-n个 n*硬币数值<=amount）
    public static int method1(int amount, int[] coins, int end) {
        if (end == coins.length) {
            return amount == 0 ? 1 : 0;
        }
        int res = 0;
        //为什么这边j从0开始  自己一开始写的时候一直觉得是从1开始才对 也就是至少要有一枚新开放的硬币
        //其实这里就应该从0开始  可以假设从开放的硬币是最后一枚硬币，那么组合当中一定要有他没有参与的组合
        //这样的组合才是完整的
        for (int j = 0; amount - coins[end] * j >= 0; j++) {
            res += method1(amount - coins[end] * j, coins, end + 1);
        }
        return res;
    }

    //记忆搜索
    public static int method2(int amount, int[] coins, int end) {
        int[][]dp=new int[amount+1][coins.length];
        for(int i=0;i<=amount;i++){
            for(int j=0;j<coins.length;j++){
                dp[i][j]=-1;
            }
        }
        return process(amount,coins,end,dp);
    }

    public static int process(int amount, int[] coins, int end,int[][]dp) {
        if (end == coins.length) {
            return amount == 0 ? 1 : 0;
        }
        if(dp[amount][end]!=-1){
            return dp[amount][end];
        }
        int res = 0;
        for (int j = 0; amount - coins[end] * j >= 0; j++) {
            res += process(amount - coins[end] * j, coins, end + 1,dp);
        }
        dp[amount][end]=res;
        return dp[amount][end];
    }

    //严格表依赖
    public static int method3(int amount, int[] coins) {
        int end=coins.length;
        int[][]dp=new int[amount+1][end];
        //初始化
        for(int i=1;coins[end-1]*i<=amount;i++){
            dp[coins[end-1]*i][end-1]=1;
        }
        for(int i=0;i<end;i++){
            dp[0][i]=1;
        }

        for(int i=1;i<=amount;i++){
            for(int j=end-2;j>=0;j--){
                for (int k = 0; i - coins[j] * k >= 0; k++) {
                   dp[i][j]+=dp[i - coins[j] * k] [j+1];
                }
            }
        }
        return dp[amount][0];
    }

    //leetcode 题解
    //思路：利用 硬币顺序来确保没有重复排列
    //例如，coins=[1,2]，对于 dp[3]的计算，一定是先遍历硬币面额 1后遍历硬币面额2，只会出现以下2 种组合：
    //3=1+1+1
    //3=1+2
    //硬币面额 2 不可能出现在硬币面额 1之前，即不会重复计算 3=2+1的情况。

    // 假设coins = {1, 2, 3}，amount = 5。 凑出5的方案有三类：
    // 组合必须以硬币1结尾，且不能包含硬币1之后的其他硬币2， 3。假设这类方案数量为x1。
    // 组合必须以硬币2结尾，且不能包含硬币2之后的其他硬币3。假设这类方案数量为x2。
    // 组合必须以硬币3结尾。假设这类方案数量为x3。
    // 最终返回x1 + x2 + x3。
    public static int method4(int amount, int[] coins) {
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for (int coin : coins) {
            for (int i = coin; i <= amount; i++) {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }

}
